The present invention relates to flow control in ATM switches and, more particularly, to methods and devices for fairly allocating bandwidth during peak traffic periods among the virtual connections sharing the output resources of ATM switches.
An asynchronous transfer mode (ATM) switch accepts cells from many source input ports and routes them to many destination output ports. An ATM switch may be hardware-based or software-based. The architecture can be generalized as shown in FIG. 1. Cells arrive on input ports IP0 to IPN and are switched through a switch fabric 100 to various ones of output ports OP0 to OPN. Each cell is transmitted on a virtual connection, “VC” for short, a plurality of which share the resources of the input ports and output ports.
A significant technical challenge facing ATM switch designers is how to allocate the output port bandwidth of an ATM switch during peak traffic periods. During such periods, the rate at which cells destined for a particular output port arrive at the aggregate of input ports may far exceed the bandwidth of the output port. This excess demand for output port bandwidth creates the need to temporarily buffer cells. Even with buffering, cell backlog may exceed buffer capacity, requiring cells to be dropped. And even if buffer capacity is sufficient, the buffered cells may face protracted delays. Thus, many ATM switches implement congestion control strategies designed to reduce cell drop and cell delay and ensure that the most critical cells are delivered in a timely manner.
Various congestion control strategies have been implemented, including input buffering with input control, output buffering with output control and dynamic input buffering with output control, or DIBOC. “Control” in this context typically refers to, among other things, a priority- and/or port-based cell release algorithm defining the order in which buffered cells are allocated output port bandwidth. In a DIBOC-based ATM switch, for example, each arriving cell is buffered at an input. An input control unit then generates and transmits a “Request” asking permission to release the cell to the destination output. The destination output monitors its bandwidth availability and eventually responds to the “Request” with a “Grant” permitting the input to release the cell. The order in which “Grants” are issued is typically governed by a policy-based cell release algorithm. Particularly advantageous DIBOC-based switches and cell release algorithms which grant “Requests” based on cell priority while treating inputs generally as peers, are taught in Khacherian, et al., application Ser. No. 08/679,360 filed Jul. 11, 1996, which is assigned to the assignee hereof.
While priority- and port-based congestion control strategies have proven useful in ameliorating some output port bandwidth allocation problems experienced in ATM switches during peak traffic periods, such strategies have failed to provide a complete solution. In real-world ATM switches, output port congestion is often caused at the connection level by the high-rate flooding of non-critical cells on a single or a small number of “problem” virtual connections. Unless the tide of cells transmitted on such “problem” virtual connections is successfully stemmed, cells transmitted on other virtual connections sharing output port resources with the “problem” virtual connections may be dropped at an unacceptable rate, or suffer unacceptable delays. This cell flooding problem may be detrimental to all virtual connections which must share output port resources with a “problem” virtual connection but may be particularly problematic for virtual connections in DIBOC-based ATM switches which must share input port resources with a “problem” virtual connection and, therefore, must compete directly with the “problem” virtual connection for both buffer space and output port bandwidth.
One way the prior art has addressed the issue of “problem” virtual connections is by separately buffering inbound cells by virtual connection, “problem” or not, and treating all virtual connections generally as peers for purposes of allocating output port bandwidth. While such “per VC queueing” strategies may be suitable in ATM switches which service a relatively small number of virtual connections, the requirement of buffering cells on a “per VC” basis means that “per VC queueing” does not scale well to ATM switches in which the number of virtual connections is relatively large. Accordingly, a need has arisen for a connection-based congestion control strategy which address the output port bandwidth allocation problems caused by “problem” virtual connections without introducing the known scalability problems of “per VC queueing”.